package com.tgy.back.tracking;

/**
 * @Author: tgy
 * @Date: 2020-11-02 10:15
 */
public class Queens01 {

    private int[] locals;

    /**
     * 指定列上面是否有皇后
     */
    private boolean[] colIsQueen;

    /**
     * 左斜对角线
     */
    private boolean[] leftOblique;

    /**
     * 右斜对角线
     */
    private boolean[] rightOblique;

    private int ranks;

    public int queens(int n) {

        if (n <= 0) {

            return 0;
        }

        if (n == 1) {

            return 1;
        }

        locals = new int[n];
        colIsQueen = new boolean[n];
        leftOblique = new boolean[(n<<1) - 1];
        rightOblique = new boolean[leftOblique.length];

        find(0);
        return ranks;
    }

    public void printQueen() {

        for (int i = 0; i < locals.length; i++) {

            for (int j = 0; j < locals.length; j++) {

                if (locals[i] == j) {
                    System.out.print(" 1 ");
                }else {

                    System.out.print(" 0 ");
                }
            }
            System.out.println();
        }
        System.out.println("=======");
    }

    private void find(int n) {

        if (n == colIsQueen.length) {

            ranks++;
            printQueen();
            return;
        }

        for (int col = 0; col < colIsQueen.length ; col++) {

            int left = colIsQueen.length - 1 + n - col;
            int right = n + col;
            if (isQueen(col,left,right)) {

                setLocations(col,left,right,true);
                locals[n] = col;
                find(n + 1);
                setLocations(col,left,right,false);
            }

        }

    }

    private boolean isQueen(int col, int left, int right) {

        if (colIsQueen[col] || leftOblique[left] || rightOblique[right]) {
            return false;
        }

        return true;
    }

    private void setLocations(int col,int left, int right, boolean flag) {

        colIsQueen[col] = flag;
        leftOblique[left] = flag;
        rightOblique[right] = flag;
    }
}
